# 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
#  设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
#  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
#
#  示例 1：
# 输入：k = 2, prices = [2,4,1]
# 输出：2
# 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
#
#  示例 2：
# 输入：k = 2, prices = [3,2,6,5,0,3]
# 输出：7
# 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
#      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3。
from typing import List


class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        """
        动态规划：根据LeetCode123 可以得出
        每一天结束之后，有可能处于以下 (2k + 1) 种状态之一：
            1:没有买股也没有卖股。
            2:买了第一支股，但是还没有卖出第一支股。
            3:买了第一支股，并且卖出第一支股。
            4:买了第一支股，并且卖出第一支股，买了第二支股，但是还没有卖出第二支股。
            5:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股。
            ...
            2k:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股... 买了第 k 支股，但是还没有卖出
            2k + 1:买了第一支股，并且卖出第一支股，买了第二支股，并且卖出第二支股... 买了第 k 支股，并且卖出第 k 支股
        :param k:
        :param prices:
        :return:
        """
        if not prices or len(prices) * k == 0:
            return 0
        size = len(prices)
        maxTradeCounts = min(k, size // 2)  # n 天最多只能进行 n // 2 笔交易
        # dpBuys[i][j] 表示在第 i 天(prices[0..i]) 进行恰好 j 笔交易，并且当前手上持有一支股票(已经完成了 j - 1 支股的交易，且买了第 j 支股，但还没卖出)能获得的最大利润
        # dpSells[i][j] 表示在第 i 天(prices[0..i])恰好进行 j 笔交易，并且当前手上不持有股票(已经完成了 j - 1 支股的交易，且买了第 j 支股，并且卖出第 j 支股)能获得的最大利润
        dpBuys, dpSells = [[0] * (maxTradeCounts + 1) for _ in range(size)], [[0] * (maxTradeCounts + 1) for _ in range(size)]
        for j in range(maxTradeCounts):
            dpBuys[0][j] = -prices[0]
        for i in range(1, size):
            dpBuys[i][0] = max(dpBuys[i - 1][0], dpSells[i - 1][0] - prices[i])
            for j in range(1, maxTradeCounts + 1):
                dpBuys[i][j] = max(dpBuys[i - 1][j], dpSells[i - 1][j] - prices[i])
                dpSells[i][j] = max(dpSells[i - 1][j], dpBuys[i - 1][j - 1] + prices[i])
        return dpSells[-1][-1]  # 等价于 return max(dpSells[-1])

        # 空间优化写法
        # buys, sells = [-prices[0]] * (maxTradeCounts + 1), [0] * (maxTradeCounts + 1)
        # for price in prices[1:]:
        #     buys[0] = max(buys[0], sells[0] - price)
        #     for i in range(1, maxTradeCounts + 1):
        #         buys[i] = max(buys[i], sells[i] - price)
        #         sells[i] = max(sells[i], buys[i - 1] + price)
        # return sells[-1]  # 等价于 return max(sells)


if __name__ == "__main__":
    k, prices = 2, [3, 2, 6, 5, 0, 3]
    # k, prices = 2, [2, 4, 1]
    # k, prices = 2, []
    print(Solution().maxProfit(k, prices))
